package tiruvury.InterviewPrep.Generic;

import java.util.Hashtable;
import java.util.PriorityQueue;
import java.util.Stack;

import tiruvury.InterviewPrep.HelperClasses.MultipleComparator;
import tiruvury.InterviewPrep.HelperClasses.MultipleNode;
import tiruvury.InterviewPrep.HelperClasses.Point;

public class GenericAlgos
{
	public static double RPNCalculator(String postFixStr)
	{
		if (postFixStr == null || postFixStr.isEmpty())
		{
			return Integer.MIN_VALUE;
		}

		Stack<Double> opStk = new Stack<Double>();
		int idx = 0;
		char ch;
		double op1 = 0;
		double op2 = 0;
		double result = -1;
		while (idx < postFixStr.length())
		{
			ch = postFixStr.charAt(idx);
			if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
			{
				if (opStk.size() >= 2)
				{
					op2 = opStk.pop();
					op1 = opStk.pop();
				}
				else
				{
					return Integer.MIN_VALUE;
				}

				switch (ch)
				{
				case '+':
					result = op1 + op2;
					break;

				case '-':
					result = op1 - op2;
					break;

				case '*':
					result = op1 * op2;
					break;

				case '/':
					result = op1 / op2;
					break;

				default:
					break;
				}
				opStk.push(result);
			}
			else
			{
				/*
				 * CODINGERROR: HOW TO CONVERT DIGIT IN CHAR FORM TO INT FORM?
				 */
				double digit = ch - '0';
				if (digit >= 0 && digit <= 9)
				{
					opStk.push(digit);
				}
				else
				{
					return Integer.MIN_VALUE;
				}
			}
			idx++;
		}

		result = opStk.pop();

		return result;
	}

	public static int getIntegerValue(String str, int radix)
	{
		if (str == null || str.isEmpty())
		{
			return -1;
		}

		if (!(radix == 2 || radix == 8 || radix == 10 || radix == 16))
		{
			return -1;
		}

		/*
		 * CODING ERROR: Dont forget to sanitize input for strings. Null check,
		 * length check, trim spaces, convert to lower case.
		 */
		// str = str.trim();
		str = str.toLowerCase();

		// Build Hashtable of letter value pairs
		Hashtable<Character, Integer> lvp = new Hashtable<Character, Integer>(16);
		lvp.put('0', 0);
		lvp.put('1', 1);
		lvp.put('2', 2);
		lvp.put('3', 3);
		lvp.put('4', 4);
		lvp.put('5', 5);
		lvp.put('6', 6);
		lvp.put('7', 7);
		lvp.put('8', 8);
		lvp.put('9', 9);
		lvp.put('a', 10);
		lvp.put('b', 11);
		lvp.put('c', 12);
		lvp.put('d', 13);
		lvp.put('e', 14);
		lvp.put('f', 15);

		int result = 0;
		int i = 0;
		int value = 0;
		for (int j = str.length() - 1; j >= 0; j--)
		{
			value = getLetterValue(str.charAt(j), radix, lvp);
			if (value == -1)
			{
				return -1;
			}

			value = (int) Math.pow(radix, i) * value;
			result = result + value;
			i++;
		}

		return result;
	}

	private static int getLetterValue(char ch, int radix, Hashtable<Character, Integer> ht)
	{
		int letterValue = -1;

		if (ht.containsKey(ch))
		{
			letterValue = ht.get(ch);
			if ((radix < 16 && letterValue > 9) || (radix < 10 && letterValue > 7) || (radix < 8 && letterValue > 2))
			{
				letterValue = -1;
			}
		}

		return letterValue;
	}

	public static boolean isStringANumber(String str)
	{
		if (str != null)
		{
			// Trim all leading and trailing spaces
			str = str.trim();

			char ch;
			boolean hasPeriod = false;
			for (int i = 0; i < str.length(); i++)
			{
				ch = str.charAt(i);
				if (isValidChar(ch, i, str.length() - 1))
				{
					if (ch == '.')
					{
						if (!hasPeriod)
						{
							hasPeriod = true;
							String postDecimalString = str.substring(i + 1);
							if (postDecimalString.length() <= 1 && !postDecimalString.equals("0"))
							{
								return false;
							}
						}
						else
						{
							// Second period found. Number invalid;
							return false;
						}
					}
				}
				else
				{
					// Invalid Character. Not a number.
					return false;
				}
			}
			return true;
		}

		return false;
	}

	private static boolean isValidChar(char ch, int index, int maxIndex)
	{
		boolean isValid = false;

		switch (ch)
		{
		case '0':
		case '1':
		case '2':
		case '3':
		case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9':
			isValid = true;
			break;
		case '+':
		case '-':
			isValid = (index == 0);
			break;
		case '.':
			isValid = (index != 0 && index != maxIndex);
			break;
		default:
			isValid = false;
			break;
		}

		return isValid;
	}

	public static void printMultiples(int[] num, int min, int max)
	{
		/*
		 * SYNTAX: When implementing a heap with a custom comparator, specify
		 * size also in the constructor
		 */
		PriorityQueue<MultipleNode> heap = new PriorityQueue<MultipleNode>(num.length, new MultipleComparator());

		// Prepopulate the heap
		for (int i = 0; i < num.length; i++)
		{
			heap.offer(new MultipleNode(num[i], num[i]));
		}

		int prevMultiple = -1;
		int currMultiple = -1;
		MultipleNode node = null;
		System.out.println("Printing Multiples: ");
		while (true)
		{
			node = heap.poll();
			if (node == null || node.multiple > max)
				break;
			heap.offer(new MultipleNode(node.multiple + node.number, node.number));

			currMultiple = node.multiple;
			if (currMultiple > min && prevMultiple != currMultiple)
			{
				System.out.print(currMultiple + ", ");
				prevMultiple = currMultiple;
			}
		}
	}

	public static void ShuffleCards()
	{
		int[] cardDeck = new int[52];

		/* initialize the card deck */
		System.out.println();
		System.out.print("Card Deck before shuffle: {");
		for (int i = 0; i < 52; i++)
		{
			cardDeck[i] = i + 1;
			System.out.print(cardDeck[i] + ", ");
		}
		System.out.println("}");

		/* Shuffle cards */
		int temp = 0;
		int randIdx = -1;
		for (int i = 0; i < 52; i++)
		{
			/*
			 * CODINGERROR: Random function is Math.random(). Note, full word
			 * random and small r
			 */
			double randNum = Math.random();
			randIdx = (int) (randNum * (52 - i));

			/*
			 * CODINGERROR: Idiot when you know you've to swap with the last
			 * element,
			 * why were you swapping with cardDeck[i] and not cardDeck[52 - i]?
			 * 
			 * Again idiot, why swap with cardDeck[52 -i]? You have to with [51
			 * - i]
			 */
			temp = cardDeck[randIdx];
			cardDeck[randIdx] = cardDeck[51 - i];
			cardDeck[51 - i] = temp;
		}

		/* Print cards */
		System.out.print("Card Deck after shuffle: {");
		for (int i = 0; i < 52; i++)
		{
			System.out.print(cardDeck[i] + ", ");
		}
		System.out.println("}");

	}

	/* Get counts of possibilities if a child can jump 1, 2 or 3 steps at a time */
	public static int GetNumSteps(int n, int[] arr)
	{
		if (arr[n - 1] != 0)
		{
			return arr[n - 1];
		}

		if (n == 3)
		{
			arr[2] = 4;
			return 4;
		}
		if (n == 2)
		{
			arr[1] = 2;
			return 2;
		}
		if (n == 1)
		{
			arr[0] = 1;
			return 1;
		}

		arr[n - 1] = GetNumSteps(n - 1, arr) + GetNumSteps(n - 2, arr) + GetNumSteps(n - 3, arr);
		return arr[n - 1];
	}

	public static void GetStepsConfiguration(int n)
	{

		int[] config = new int[n];

		System.out.println("Possible Configurations are: ");
		GetStepsConfig(n, config, 0);
	}

	private static void GetStepsConfig(int rem, int[] config, int idx)
	{
		if (rem == 0)
		{
			System.out.print("{ ");
			/*
			 * CODINGERROR
			 * 1. DO NOT PRINT EVERYTHING from 0 to config.length - only till
			 * IDX. That will just give the configuration and not the entire
			 * array with possible junk values.
			 * 2. Print only UPTO idx as idx is always incremented after
			 * assignment.
			 */
			for (int i = 0; i < idx; i++)
			{
				System.out.print(config[i] + ", ");
			}
			System.out.println(" }");
		}

		if (rem > 0)
		{
			int newRem = 0;
			int newIdx = 0;
			for (int j = 1; j <= 3; j++)
			{
				newIdx = idx;
				newRem = rem - j;
				/*
				 * CODINGERROR: ALWAYS MAKE SURE YOU DONT OPERATE ON THE PARAMS
				 * PASSED IN!
				 * You were directly manipulating idx without caching it in
				 * newIdx. That will
				 * change the value of idx across iterations in this for loop.
				 */
				config[newIdx++] = j;
				GetStepsConfig(newRem, config, newIdx);
			}
			idx++;
		}
	}

	public static double FindAngleBetweenHands(int hrs, int mins)
	{
		double hrAngPerMin = 0.5;
		double minAngPerMin = 6;

		double hrAngle = (hrs * 60 + mins) * hrAngPerMin;
		double minAngle = mins * minAngPerMin;

		double diffAngle = Math.abs(hrAngle - minAngle);

		if (diffAngle > 180)
		{
			diffAngle = 360 - diffAngle;
		}

		return diffAngle;
	}

	public static void CheckTicTacToeWin(int[][] board)
	{
		int maxIdx = board.length - 1;
		for (int i = 0; i <= maxIdx; i++)
		{
			if (i == 0)
			{
				CheckTriplet(board, new Point(1, 1), new Point(0, 0), maxIdx);
			}

			if (i == maxIdx)
			{
				CheckTriplet(board, new Point(1, maxIdx - 1), new Point(0, maxIdx), maxIdx);
			}

			CheckTriplet(board, new Point(i, 1), new Point(i, 0), maxIdx);
			CheckTriplet(board, new Point(1, i), new Point(0, i), maxIdx);
		}
	}

	private static void CheckTriplet(int[][] board, Point currPt, Point prevPt, int maxIdx)
	{
		if (currPt != null && prevPt != null)
		{
			if (currPt.x <= maxIdx && currPt.y <= maxIdx)
			{
				if (board[currPt.x][currPt.y] == board[prevPt.x][prevPt.y])
				{
					CheckTriplet(board, new Point(currPt.x + (currPt.x - prevPt.x), currPt.y + (currPt.y - prevPt.y)), currPt, maxIdx);
					if ((currPt.x == maxIdx) || (currPt.y == maxIdx))
					{
						System.out.println("Winning triplet found.");
					}
				}
			}
		}

		return;
	}

	public static String GetNumInWords(int num)
	{
		Hashtable<Integer, String> ht = new Hashtable<Integer, String>();
		ht.put(new Integer(0), "Zero");
		ht.put(new Integer(1), "One");
		ht.put(new Integer(2), "Two");
		ht.put(new Integer(3), "Three");
		ht.put(new Integer(4), "Four");
		ht.put(new Integer(5), "Five");
		ht.put(new Integer(6), "Six");
		ht.put(new Integer(7), "Seven");
		ht.put(new Integer(8), "Eight");
		ht.put(new Integer(9), "Nine");
		ht.put(new Integer(10), "Ten");

		ht.put(new Integer(11), "Eleven");
		ht.put(new Integer(12), "Twelve");
		ht.put(new Integer(13), "Thirteen");
		ht.put(new Integer(14), "Fourteen");
		ht.put(new Integer(15), "Fifteen");
		ht.put(new Integer(16), "Sixteen");
		ht.put(new Integer(17), "Seventeen");
		ht.put(new Integer(18), "Eighteen");
		ht.put(new Integer(19), "Nineteen");
		ht.put(new Integer(20), "Twenty");

		ht.put(new Integer(30), "Thirty");
		ht.put(new Integer(40), "Fourty");
		ht.put(new Integer(50), "Fifty");
		ht.put(new Integer(60), "Sixty");
		ht.put(new Integer(70), "Seventy");
		ht.put(new Integer(80), "Eighty");
		ht.put(new Integer(90), "Ninety");

		ht.put(new Integer(100), "Hundred");
		ht.put(new Integer(1000), "Thousand");

		return GetNumAsWord(new Integer(num), ht);
	}

	private static String GetNumAsWord(Integer n, Hashtable<Integer, String> ht)
	{
		StringBuffer sb = new StringBuffer();

		int divisor = 1;
		int num = n.intValue();
		if (num >= 1000)
		{
			divisor = 1000;
		}
		else if (num >= 100)
		{
			divisor = 100;
		}
		else if (num >= 10)
		{
			divisor = 10;
		}

		int quotient = num / divisor;
		int remainder = num % divisor;

		if (num >= 100)
		{
			sb.append(GetNumAsWord(new Integer(quotient), ht));
			sb.append(" " + ht.get(new Integer(divisor)));
			if (remainder > 0)
			{
				sb.append(GetNumAsWord(new Integer(remainder), ht));
			}
		}
		else
		{
			if (num > 20)
			{
				sb.append(" " + ht.get(new Integer(quotient * divisor)));
				if (remainder > 0)
				{
					sb.append(GetNumAsWord(new Integer(remainder), ht));
				}
			}
			else
			{
				sb.append(" " + ht.get(new Integer(num)));
			}
		}

		return sb.toString();
	}

	public static String GetRomanNotation(int num)
	{
		if (num > 1000)
		{
			System.out.println("print a number between 1 and 1000");
		}

		char[] letters = new char[]
		{ 'I', 'V', 'X', 'L', 'C', 'D', 'M' };
		int[] indices = new int[]
		{ 0, 2, 4, 6 };
		int exp = 3;

		return GetRoman(num, letters, indices, exp, "");

	}

	private static String GetRoman(int num, char[] letters, int[] indices, int exp, String romanNotation)
	{
		if (num == 0)
		{
			return romanNotation;
		}

		int q = 0;
		int r = 0;
		int pow = 0;

		while (exp >= 0)
		{
			pow = (int) Math.pow(10, exp);
			q = num / pow;
			r = num % pow;

			if (q > 0)
				break;
			exp--;
		}

		String currentPowLetter = Character.toString(letters[indices[exp]]);
		String middleLetter = Character.toString(letters[indices[exp] + 1]);
		String nextPowLetter = Character.toString(letters[indices[exp] + 2]);
		if (q == 4)
		{
			romanNotation += (currentPowLetter + middleLetter);
		}
		/*
		 * CODINGERROR:
		 * Mistake 1: You said if q== 4 || q == 9. Great. You knew they hand to
		 * be handled differently. But once you bucketed them, you just said
		 * currenPowLetter + nextPowLetter for both, which was wrong.
		 * Mistake 2: You realized Mistake 1, copy pasted if q== 4 and just said
		 * if q == 9 below. Missed the else if. So incorrect output again.
		 */
		else if (q == 9)
		{
			romanNotation += (currentPowLetter + nextPowLetter);
		}
		else if (q == 5)
		{
			romanNotation += middleLetter;
		}
		else
		{
			if (q > 5)
			{
				romanNotation += middleLetter;
				q = q - 5;
			}

			for (int i = 0; i < q; i++)
			{
				romanNotation += currentPowLetter;
			}
		}

		return GetRoman(r, letters, indices, exp, romanNotation);
	}

	public static int RomanToInt(String romanString)
	{
		int num = 0;
		int prev = 0;
		int curr = 0;

		Hashtable<Character, Integer> ht = new Hashtable<Character, Integer>();
		ht.put('I', new Integer(1));
		ht.put('V', new Integer(5));
		ht.put('X', new Integer(10));
		ht.put('L', new Integer(50));
		ht.put('C', new Integer(100));
		ht.put('D', new Integer(500));
		ht.put('M', new Integer(1000));

		for (int i = 0; i < romanString.length(); i++)
		{
			/*
			 * CODINGERROR
			 * No error here but watch out for how to put/get/box/unbox
			 * hashtable values
			 */
			curr = ((Integer) ht.get(new Character(romanString.charAt(i)))).intValue();
			if (curr > prev)
			{
				num = num - prev;
				num = num + (curr - prev);
			}
			else
			{
				num = num + curr;
			}
			prev = curr;
		}

		return num;
	}
}
